#include <iostream>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <math.h>
using namespace std;

int a[1024];//待排序数组
int b[1024];//合并结果

void Merge(int a[], int b[], int left, int mid, int right) //合并两个有序数组，存储到b数组
{	
	int p = left, q = mid+1;// p是a数组左区间的下标，q是a数组右区间的下标
	int k = 0;// k是合并数组b的下标
	while(p <= mid && q <= right) 
    {
		if(a[p] < a[q])
        {
			b[k++] = a[p++];
		}
        else
        {
			b[k++] = a[q++];
		}
	}

	while(p <= mid)
        b[k++] = a[p++];
    while(q <= right)
        b[k++] = a[q++];
}

void copy(int a[], int b[],int left,int right) 
{
	for(int i = left; i <= right; i++) {
		a[i] = b[ i- left];// a数组下标从left开始 ，b数组下标从0开始
	}
}

void MergeSort(int a[], int left, int right) {
    if (left < right) //至少有2个元素
    { 				
        int i = (left + right) / 2; //取中点
        MergeSort(a, left, i); //左区间
        MergeSort(a, i + 1, right); //右区间
        Merge(a, b, left, i, right);//合并到数组b
        copy(a, b, left, right);//复制回数组a
    }
}

int main() {
    int n, i;
    cout << "输入待排序元素的个数：";
    cin >> n;
    cout << "输入待排序元素：";
    for (i = 0; i < n; i++) {
        cin >> a[i];
    }
	MergeSort(a, 0, n - 1);
    cout << "排序后的序列为:";
    for(i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	return 0;
}
